from functools import cache
from typing import List

temp = '''

'''
EACH = 233
MOD = 10**9 + 7
INT = 10**6

#题目2999 2376
class NumberDp:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        number_start = str(start)
        number_finish = str(finish)
        dec_length = len(number_finish) - len(number_start)
        number_start = '0' * dec_length + number_start
        number_length = len(number_finish)

        limit_length = len(number_finish) - len(s)

        def dfs(index: int, is_low: bool, is_limit: bool, number_list: List) -> int:
            if index == number_length:
                print(number_list)
                return 1
            res = 0

            low = ord(number_start[index]) - 48 if is_low else 0
            high = ord(number_finish[index]) - 48 if is_limit else 9

            if index < limit_length:
                for i in range(low, min(high, limit) + 1):
                    number_list.append(i)
                    res += dfs(index + 1, is_low and i == low, is_limit and i == high, number_list)
                    number_list.pop()
            else:
                s_num = ord(s[index-limit_length]) - 48
                if low <= s_num <= min(high, limit):
                    number_list.append(s_num)
                    res += dfs(index + 1, is_low and s_num == low, is_limit and s_num == high, number_list)
                    number_list.pop()
            return res
        return dfs(0, True, True, [])

